package com.scqzy.shengchunqiang.sword2offer.day17;

import java.util.Arrays;

/**
 * @Description: 剑指 Offer 40. 最小的k个数
 * @Author 盛春强
 * @Date 2021/8/24 14:22
 */
public class GetLeastNumbers {
    /**
     * 中断选择排序
     *
     * @Author 盛春强
     * @Date 2021/8/24 14:36
     * @Param [arr, k]
     * @Return int[]
     */
    public int[] getLeastNumbers1(int[] arr, int k) {
        int[] res = new int[k];
        for (int i = 0; i < arr.length && i < k; i++) {
            int min = arr[i];
            int tmpPos = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < min) {
                    min = arr[j];
                    tmpPos = j;
                }
            }
            arr[tmpPos] = arr[i];
            res[i] = min;
            if (i == k - 1) {
                break;
            }
        }
        return res;
    }

    /**
     * 计数排序
     *
     * @Author 盛春强
     * @Date 2021/8/24 14:37
     * @Param [arr, k]
     * @Return int[]
     */
    public int[] getLeastNumbers2(int[] arr, int k) {
        int[] bucket = new int[10001];
        for (int i : arr) {
            bucket[i]++;
        }
        int[] res = new int[k];
        int p = 0;
        for (int i = 0; i < bucket.length; i++) {
            while (bucket[i]-- > 0 && p < k) {
                res[p++] = i;
            }
            if (p == k) {
                return res;
            }
        }
        return res;
    }

    /**
     * 快排
     *
     * @Author 盛春强
     * @Date 2021/8/24 14:55
     * @Param [arr, k]
     * @Return int[]
     */
    public int[] getLeastNumbers3(int[] arr, int k) {
        if (k == 0) {
            return new int[0];
        }
        return quickSort(arr, 0, arr.length - 1, k - 1);
    }

    private int[] quickSort(int[] arr, int left, int right, int k) {
        int pivotPosition = quickPartition(arr, left, right);
        /*
        基准坐标左侧均比基准坐标的值小，根据题意无需排序前k个值
         */
        if (pivotPosition == k) {
            return Arrays.copyOf(arr, k + 1);
        }
        return pivotPosition > k ? quickSort(arr, left, pivotPosition - 1, k) : quickSort(arr, pivotPosition + 1, right, k);
    }

    private int quickPartition(int[] arr, int left, int right) {
        int pivot = arr[left];
        while (left < right) {
            while (arr[right] >= pivot && left < right) {
                right--;
            }
            arr[left] = arr[right];
            while (arr[left] <= pivot && left < right) {
                left++;
            }
            arr[right] = arr[left];
        }
        arr[left] = pivot;
        return left;
    }
}
